Many of the tasks that are addressed by decision-making systems and artificial intelligence can be represented as constraint satisfaction problems (CSPs). In this representation, the task is specified in terms of a set of variables, each of which can assume values in a given domain, and a set of constraints that the variables must simultaneously satisfy. The set of variables, domains and constraints is referred to as a CSP. Each constraint may be expressed as a relation, defined over some subset of the variables, denoting valid combinations of their values. A solution to a CSP is an assignment of a value to each variable from its domain that satisfies all of the constraints. Various techniques have been proposed for solving CSPs. A survey of common techniques can be found in a paper by Kumar entitled “Algorithms for Constraint Satisfaction Problems: A Survey,” Artificial Intelligence Magazine, 13:1 (1992), pages 32-44, which is incorporated herein by reference.
Constraint satisfaction methods have been found useful in a variety of applications, including:                Artificial intelligence        Robotic control        Temporal reasoning        Natural language parsing        Spatial reasoning        Test-case generation for software and hardware systems        Machine vision        Medical diagnosis        Resource allocation        Crew scheduling        Time tabling        Frequency allocation        Graph coloring.        
For example, Bin et al. describe a constraint satisfaction method for use in automated generation of test programs, in a paper entitled “Using a Constraint Satisfaction Formulation and Solution Techniques for Random Test Program Generation,” IBM Systems Journal 41:3 (2002), pages 386-402, which is incorporated herein by reference. The authors show how random test program generation can be modeled as a CSP, and they describe a set of solution techniques that are used in practical test-case generation tools. Adir et al. in a paper entitled “Piparazzi: A Test Program Generator for Micro-architecture Flow Verification,” Eighth IEEE International High-Level Design Validation and Test Workshop (Nov. 12-14, 2003), pages 23-28, which is incorporated herein by reference, describe a test generator that uses a dedicated CSP solver. The test generator converts user requests for micro-architectural events into test programs.
A number of other constraint satisfaction systems are described in the patent literature. For example, U.S. Pat. No. 5,636,328, whose disclosure is incorporated herein by reference, describes methods and apparatus for finding values that satisfy a set of constraints, applied particularly to control of a robotic arm. U.S. Pat. No. 5,617,510, whose disclosure is also incorporated herein by reference, describes a method, useful in computer-aided design, of identifying possible solutions to an over-constrained system having a collection of entities and constraints.
The concept of a CSP was generalized by Mittal et al. to cover more complex problems, in which variables may be active or inactive, in a paper entitled “Dynamic Constraint Satisfaction Problems,” Proceedings of the Eighth National Conference on Artificial Intelligence (AAAI-90), Boston, Mass., July 1990, pages 25-32, which is incorporated herein by reference. To avoid ambiguity, this generalization is commonly referred to as “Conditional CSP,” or CondCSP. A CondCSP comprises the following:                A set of variables V={v1, v2, . . . , vn}.        A set of domains D={D1, D2, . . . , Dn}, such that Di is the set of valid values for the variable vi.        A set of initial variables VI⊂V, VI≠φ.        A set of compatibility constraints CC.        A set of activity constraints CA.        
In contrast to the traditional definition of CSP, a variable in a CondCSP can be either active or inactive. A variable is assigned a value only if it is active. A compatibility constraint specifies the set of allowed combinations of values for a set of variables. A compatibility constraint is active only if all its variables are active. An activity constraint has the form cact→v, in which c is defined in the same manner as a compatibility constraint, and v is a variable. Such an activity constraint states that if the left hand constraint c holds, then the variable v is active. Similarly, crn→v (wherein rn stands for “require not”) states that the variable v is not active if constraint c holds.
A Solution to a CondCSP contains (a) a set of active variables that must include all initial variables, and (b) a value assignment to all the active variables, in which each variable is assigned a value from its domain, the assignment satisfying all the active compatibility constraints. The assignment and the set of active variables must satisfy all the activity constraints.